#include <iostream>
#include <fstream>
#include <stdlib.h>
#include <list>
#include <vector>
#include <string>

using namespace std;

// Retorna el elemento del medio
int medio(int a, int b, int c){
	int res;
    if (a >= b){
		if (a >= c){ // a >= b,c
			b >= c ? res = b :  res =c;	
		} else{ // b <= a < c
			res = a;
		}
    } else{ // a < b
		if (b >= c){ //c, a <= b
			(a >= c) ?	res = a : res = c;
		} else{ // a < b < c
			res = b;
		}
    }
    return res;
}
// Aproximacion de la mediana.
static int pivote(int P[],int SA[], int h, int i, int j) {
	int prin; 
	int med; 
	int fin;
	int s;
	int n = j-i;
   
	if (n <= 1) return P[SA[i] + h]; 
   
	med = P[SA[i + ((j - i) / 2)] + h];              
   
	if (n > 7){
		prin = P[SA[i]+ h];
		fin = P[SA[j]+ h];
		if (n > 40){         
			s = n/8;
			prin = medio(P[SA[i] + h], P[SA[i + s] + h], P[SA[i + s + s] + h]);
			med = medio(P[SA[i + ((j - i) / 2) - s] + h],P[SA[i + ((j - i) / 2)] + h],P[SA[i + ((j - i) / 2) + s] + h]);
			fin = medio(P[SA[i - s - s] + h], P[SA[i - s] + h],P[SA[j]+ h]);
		}
		med = medio(prin, med, fin);      
   }
   return med;
}

// Implementacion de qsort ternario.
void q3sort(int P[], int  SA[], int i, int j, int h){
    list<int> iguales; // Lista de elementos iguales al pivot.
    list<int> menores; // Lista de elementos menores al pivot.
    list<int> mayores; // Lista de elementos mayores al pivot.
    list<int>::iterator elem;
    int inicioIguales; // Posicion de inicio de los elementos iguales al pivot en el arreglo.
    int finIguales; // Posicion final de los elementos iguales al pivot.
    int tamIguales; // Tamaño de los elementos iguales al pivot.
    int tamMenores; // Tamaño de los elementos menores al pivot.
    
    // Fin de la recursion
    if (j < i) return;
    
    int pos = i; 
    int pivot = pivote(P, SA, h, i, j);
    
    for (int k = i; k <= j; k++){ // Se divide en mayores, iguales o menores al pivot.
		if(P[SA[k]+h] < pivot){
			menores.push_back(SA[k]);     
		} else{
			if(P[SA[k]+h] == pivot){
				iguales.push_back(SA[k]);
			} else{
				mayores.push_back(SA[k]);
			}
		}
    }
    
    tamMenores = menores.size();
    tamIguales = iguales.size();
    
    elem = menores.begin();
    while( elem != menores.end()){ //Se agregan los menores al vector.
		SA[pos] = *elem;
		elem++;
		pos++; 	
    }
    
    elem = iguales.begin();
    while( elem != iguales.end()){// Se agregan los iguales al vector.
		SA[pos] = *elem;
		elem++;
		pos++;
    }
    
    elem = mayores.begin();
    while( elem != mayores.end()){ // Se agregan los mayores al vector.
		SA[pos] = *elem;
		elem++;
		pos++; 
    }

	// LLamada recursiva a los menores.
    q3sort(P, SA, i, i+(tamMenores-1), h);	    
    
    inicioIguales = i + tamMenores;
    finIguales = inicioIguales + tamIguales -1 ;
    
    //Se actualiza el numero de bloque de los elementos iguales.
    for(int k = inicioIguales ; k <= finIguales ; k++){ 
	    P[SA[k]] = finIguales;
    }
    // Si es un grupo ordenado se setea la longitud en -1.
    if (tamIguales == 1){
	     SA[inicioIguales] = -1; 
    }
    // LLamada recursiva a los mayores.
    q3sort(P, SA,i + tamMenores + tamIguales , j, h); 
}

// Funcion que calcula un bucket sort inicial.
void inicialBucketSort(int P[], int  SA[], int n, int max){
    list<int> vacia;
    vector< list<int> > bucket(max, vacia);
    list<int>::iterator elem;
    
    int j = 0;
    int bloque = 0;
    int temp;
    int tam;
    
    for(int i = 0; i < n; i++) bucket[P[i]].push_back(i);
    
    for(int i = 0; i < max; i++){
		temp = j;
		tam = bucket[i].size();
		bloque = j + tam - 1;
		elem = bucket[i].begin();
		while( elem != bucket[i].end()){ 
			SA[j] = *elem;
			P[SA[j]] = bloque;
			elem++;
			j++; 
		}
	   
		if (tam == 1) SA[j] = -1;
    }
}

// Funcion que calcula el suffix array y el vector inverso.
void suffixArray(int  P[], int  SA[], int n,  int h){
    int i;
    int neg;
    int fin;

    while (SA[0] > -n) { // Sigo hasta que no son todos grupos ordenados. 
	    i = 0; 
	    neg = 0; 
        
	    while (i < n){
			if (SA[i] < 0) {
				neg += SA[i];
				i -= SA[i]; // Si es un grupo ordenado lo salto.
			} else {
				if (neg < 0) {
					SA[i+neg] = neg; // Combino los grupos ordenados anteriores a i.
					neg = 0;
				}
				fin = P[SA[i]]; 
				q3sort(P, SA, i, fin, h); //LLamada para ordenar este grupo desordenado.
				i = fin + 1; 
			}
	    }
        
	    if (neg < 0) SA[i+neg] = neg; 
	    
	    (h == 1) ? h = 2 : h = 2*h;
	}
	for (i = 0; i < n; ++i){ // Reconstruyo el suffix array.
	    SA[P[i]]=i;
	}
}
// Funcion que calcula el LCP del suffix array.
void lcp(int  P[], int  SA[], int  LCP[] ,string  &s, int n){
    int h = 0;
    int k;
    int i;
    
    LCP[P[SA[0]]] = 0;
    LCP[P[SA[1]]] = 0;
    for(i = 0; i < n; i++){
        if (P[i] > 1){
			k = SA[P[i] - 1];
			while(s[i+h] == s[k+h]) h++;
			LCP[P[i]] = h;
			if (h > 0) h--;
		}
    }
}

// Funcion que calcula la cantidad de substrings de un string dado.
long long int cantidadSubstrings(int  LCP[], int  SA[], int n){
    long long int res = 0;
    
    for(int i = 1; i < n; i++){
		res += ((n-1) - SA[i]) - LCP[i];
	}

    return res;
}

// Funcion que transforma un string en un arreglo con el numero ascii asociado a cada char.
// Funcion que llena el vector por primera vez con todos los indices de los sufijos.
// Funcion que además cuenta la cantidad de iguales al primero para ver si son todos iguales.
int llenarInicial(int SA[], string &s, int P[], int n){
	char a = s[0];
	int res = 0;		
	SA[n-1] = n-1;
	P[n-1] = 0;
	for(int i = 0; i < (n-1) ; i++){
		SA[i] = i;
		P[i] = (int) s[i] - 97 + 1;
		if(s[i] == a){
			res++;
		}
    }
    return res;
}

// Main que toma las entradas y llama a las funciones correspondientes.
int main() {
	string s;
    int casos;
    long long int res;
    int n;
    int h;
    scanf("%d", &casos);
    
    while(casos > 0){
	
		h = 0;
		cin >> s;
		s.push_back('$'); // Pongo el caracter especial al final.
		n = s.size(); 
		int SA [n]; // Suffix Array.
		int P [n]; // Vector inverso.
		int LCP [n]; // Vector LCP.
	
		// Paso a ascii los caracteres del string para la primera comparacion.
		// LLeno a inicialmente con los sufijos desordenados.
		res = llenarInicial(SA, s, P, n);
					
		if (n > res + 1){    //Si son todos iguales no opero.
			if(n < 27){
				q3sort(P, SA, 0, n-1, h);//Ordenamiento inicial.
			} else{
				// Si hay muchos elementos uso bucket sort para el primer ordenamiento.
				inicialBucketSort(P, SA, n, 27);
			}
	    
			h = 1; // luego h es 1
	
			suffixArray(P, SA, n, h); // Calculo el suffix array y el vector inverso.
			lcp(P, SA, LCP, s, n); // Calculo el LCP del suffix array.
	
			res = cantidadSubstrings(LCP, SA, n); //Calculo la cantidad de substrings.
	    }
		
		printf("%lld \n", res);
		casos--;       
    } 
    return 0;
}
